#include <stdlib.h>
#include <string.h>

#include "sort.h"

static int merge(void *data, int esize, int i, int j, int k, compare cmp)
{
    char *a = data, *m;
    int ipos, jpos, mpos;

    ipos = i;
    jpos = j + 1;
    mpos = 0;

    if((m = (char *)malloc(esize * ((k - i) + 1))) == NULL)
        return -1;

    while (ipos <= j || jpos <= k)
    {
        if(ipos > j)
        {
            while (jpos <= k)
            {
                memcpy(&m[mpos * esize], &a[jpos * esize], esize);
                jpos++;
                mpos++;
            }
            continue;
        }
        else if (jpos > k)
        {
            /*  The right division has no more elements to merge. */
            while (ipos <= j)
            {
	        memcpy(&m[mpos * esize], &a[ipos * esize], esize);
	        ipos++;
	        mpos++;
	    }
	    continue;
        }

        /* Append the next ordered element to the merged elements. */
        if(cmp(&a[ipos * esize], &a[jpos * esize]) < 0)
        {
            memcpy(&m[mpos * esize], &a[ipos * esize], esize); 
	    ipos++;
	    mpos++;
        }
        else
        {
            memcpy(&m[mpos * esize], &a[jpos * esize], esize); 
	    jpos++;
	    mpos++;
        }
    }

    memcpy(&a[i * esize], m, esize * ((k - 1) + 1));

    free(m);

    return 0;
}

int mgsort(void *data, int size, int esize, int i, int k, compare cmp)
{
    int j;

    /* Sort the recursion when no more divisions can be made. */
    if(i < k)
    {
        j = (int)((i + k - 1) / 2);

        if (mgsort(data, size, esize, i, j, cmp) < 0)
            return -1;
            
        if (mgsort(data, size, esize, j + 1, k, cmp) < 0)
            return -1;
        
        if (mgsort(data, esize, i, j, k, cmp) < 0)
            return -1;
    }

    return 0;
}
